﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.ListNode707
{
    // ==================================================== 力扣707.设计链表
    //设计链表的实现
    //可以选择单链表或双链表。
    //实现功能：
    //get(index):获取链表中第index个节点的值，如果索引无效，则返回-1
    //addAtHead(val):在链表第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点
    //addAtTail(val):将值为val的节点追加到链表的最后一个元素
    //addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
    //deleteAtIndex(index):如果索引index有效，则删除链表中的第index个节点。
    //val在[1,1000]
    //假设链表中的所有节点都是 0-index 的。
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode prev;
        public ListNode(int val, ListNode next = null, ListNode prev = null)
        {
            this.val = val;
            this.next = next;
            this.prev = prev;
        }
    }
    class DesignListNode707
    {
        private ListNode _dymmyHead;//虚拟头节点
        private int _size;
        public DesignListNode707()
        {
            _dymmyHead = new ListNode(0);
            _size = 0;
        }

        public int Get(int index)
        {//get(index):获取链表中第index个节点的值，如果索引无效，则返回-1
            if (index < 0 || index > _size - 1)
                return -1;

            ListNode cur = _dymmyHead.next;
            while (Convert.ToBoolean(index--))//如果--index会陷入死循环
            {
                cur = cur.next;
            }
            return cur.val;
        }

        public void AddAtHead(int val)
        {//addAtHead(val):在链表第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点
            ListNode head = new ListNode(val);
            head.next = _dymmyHead.next;
            _dymmyHead.next = head;
            head.prev = _dymmyHead;
            if (head.next != null)
                head.next.prev = head;
            _size++;
        }

        public void AddAtTail(int val)
        {//addAtTail(val):将值为val的节点追加到链表的最后一个元素
            ListNode newNode = new ListNode(val);

            ListNode cur = _dymmyHead;
            while (cur.next != null)
            {
                cur = cur.next;
            }
            cur.next = newNode;
            newNode.prev = cur;
            _size++;
        }

        public void AddAtIndex(int index, int val)
        {//addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val的节点。
         //如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
            if (index == _size)
            {
                AddAtTail(val);
                return;
            }
            else if (index < 0)
            {
                AddAtHead(val);
                return;
            }
            else if (index > _size - 1)
            {
                return;
            }

            ListNode newNode = new ListNode(val);
            ListNode cur = _dymmyHead;
            while (Convert.ToBoolean(index--))
            {
                cur = cur.next;
            }

            newNode.next = cur.next;
            cur.next.prev = newNode;
            cur.next = newNode;
            newNode.prev = cur;
            _size++;
        }

        public void DeleteAtIndex(int index)
        {    //deleteAtIndex(index):如果索引index有效，则删除链表中的第index个节点。

            if (index > _size - 1 || _size < 0)
                return;

            ListNode cur = _dymmyHead;
            while (Convert.ToBoolean(index--))
            {
                cur = cur.next;
            }
            cur.next = cur.next.next;
            _size--;
        }

        public void Show()
        {
            ListNode cur = _dymmyHead;
            while (cur.next != null)
            {
                Console.WriteLine(cur.next.val);
                cur = cur.next;
            }
        }
    }
}
